
#define LEFT  0
#define RIGHT 1

typedef struct {
    struct TreeNode* node;
    unsigned long long index;
    unsigned long long type;
} DATA;

#define QLEN 65535

void ENQUEUE(DATA *q, DATA d, int *h) {
    int head = *h;
    q[head++] = d;
    head %= QLEN;
    *h = head;
}

DATA *DEQUEUE(DATA *q, int *t) {
    int tail = *t;
    DATA *d = &q[tail++];
    tail %= QLEN;
    *t = tail;
    return d;
}

#define NUMOFQUEUE (head >= tail ? head - tail : QLEN - (tail - head))

int max(int a, int b) {
    return a > b ? a :b;
}

int widthOfBinaryTree(struct TreeNode* root){
    if (root == NULL) {
        return 0;
    }

    DATA q[QLEN] = {0};
    int head = 0;
    int tail =  0;

    DATA s = {root, 0, LEFT};
    ENQUEUE(q, s, &head);

    int width = 0;

    for (int step = 0; NUMOFQUEUE != 0; step++) {
        int cnt = NUMOFQUEUE;

        unsigned long long left_index = 0;
        unsigned long long right_index = 0;
        for (int i = 0; i < cnt; i++) {
            DATA d = *DEQUEUE(q, &tail);

            unsigned long long index = d.index * 2 + d.type;
            if (i == 0) {
                left_index = index;
            }
            if (i == cnt - 1) {
                right_index = index;
            }

            if (d.node->left != NULL) {
                DATA t = {d.node->left, index, LEFT};
                ENQUEUE(q, t, &head);
            }

            if (d.node->right != NULL) {
                DATA t = {d.node->right, index, RIGHT};
                ENQUEUE(q, t, &head);
            }
        }

        width = max(width, right_index - left_index + 1);
    }

    return width;
}

